package leetcode_101_120;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;


public class zigzagLevelOrder_103 {
    /**
     *给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。
     * （即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        /**
         * 还是挺简单的，标记好每一层是第几层。对应好是第几个集合即可
         */
        List<List<Integer>> ans = new ArrayList<>();
        dfs(root, 1, ans);
        for(int i=0;i<ans.size();i++){
            if(i%2==1)
                reverse(ans.get(i));  //这里使用java封装好的 Collections.reverse方法，反而比我自己写的反转方法慢些
        }
        return ans;
    }
    /**
     * 数组反转方法
     */
    void reverse(List<Integer> list){
        List<Integer>reverse=new ArrayList<>();
        for (int i=list.size()-1;i>=0;i--)
            reverse.add(list.get(i));
        list.clear();  //清楚原有数据
        list.addAll(reverse); //填入新的数据
    }

    void dfs(TreeNode node, int k, List<List<Integer>> ans) {
        if (node == null)
            return;
        if (k > ans.size()) {  //说明此时的第k层的集合不存在
            List<Integer> list = new ArrayList<>();
            list.add(node.val);
            ans.add(list);
        } else {//存在第k层的集合，直接添加元素
            ans.get(k - 1).add(node.val);
        }
        dfs(node.left, k + 1, ans);
        dfs(node.right, k + 1, ans);
    }
}
